package j2025.j01;

import java.util.ArrayList;
import java.util.Stack;

public class j0111 {
    /**
     * 79. 单词搜索
     * 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
     *
     * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
     */
    int[] dx = new int[]{0,0,-1,1};
    int[] dy = new int[]{1,-1,0,0};
    boolean[][] vis;
    int m,n;
    public boolean exist(char[][] board, String word) {
        m =board.length;n = board[0].length;
        vis = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(board[i][j] == word.charAt(0)){
                    vis[i][j] = true;
                    if(isOrNot(board,word,i,j,1)){
                        return true;
                    }
                    vis[i][j] = false;
                }
            }
        }
        return false;
    }
    public boolean isOrNot(char[][] board, String word,int i,int j,int index) {
        if(index == word.length()){
            return true;
        }
        for (int k = 0; k < 4; k++) {
            int x = i + dx[k];
            int y = j + dy[k];
            if(x>=0 && x<m && y>=0 && y<n && !vis[x][y] && board[x][y]==word.charAt(index)){
                vis[x][y] = true;
                if(isOrNot(board,word,x,y,index+1)){
                    return true;
                }
                vis[x][y] = false;
            }
        }
        return false;
    }


    /**
     * 394. 字符串解码
     * 给定一个经过编码的字符串，返回它解码后的字符串。
     *
     * 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
     *
     * 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
     *
     * 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
     * @param s
     * @return
     */
    public String decodeString(String s) {
        Stack<StringBuilder> str = new Stack<>();
        Stack<Integer> count = new Stack<>();
        str.push(new StringBuilder());
        int i = 0;
        while(i<s.length()){
            if(s.charAt(i)>='0' && s.charAt(i)<='9'){
                int tmp = 0;
                while(s.charAt(i)>='0' && s.charAt(i)<='9'){
                    tmp = tmp*10+(s.charAt(i)-'0');
                    i++;
                }
                count.push(tmp);
            }else if(s.charAt(i)=='['){
                i++;
                StringBuilder tmp = new StringBuilder();
                while(s.charAt(i)>='a' && s.charAt(i)<='z'){
                    tmp.append(s.charAt(i));
                    i++;
                }
                str.push(tmp);
            }else if(s.charAt(i)==']'){
                StringBuilder tmp = new StringBuilder(str.peek());
                StringBuilder fz = new StringBuilder(str.pop());
                int cou = count.pop();
                for (int j = 1; j < cou; j++) {
                    tmp.append(fz);
                }
                i++;
                str.peek().append(tmp);
            }else {
                str.peek().append(s.charAt(i));
                i++;
            }
        }
        return str.peek().toString();
    }


    /**
     * 75. 颜色分类
     * 给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
     *
     * 我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
     *
     * 必须在不使用库内置的 sort 函数的情况下解决这个问题
     * @param nums
     */
    public void sortColors(int[] nums) {
        int n = nums.length;
        int left = -1,right = n;
        int i = 0;
        while (i < right) {
            if (nums[i] == 0) {
                swap(nums,i++,++left);
            }else if (nums[i] == 2) {
                swap(nums,i,--right);
            }else if (nums[i] == 1){
                i++;
            }
        }
    }
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }






























}
